/**
 * Created with IntelliJ IDEA.
 * Description:八皇后算法
 * User: xwl
 * Date: 2023-04-10
 * Time: 22:20
 */

public class EightEmpress {
    //
    int count;
    // 存放皇后的摆放位置
    int[] place;
    // 存放列的状态
    int[] flag;
    // 存放上对角线的状态
    int[] upDiagonal;
    // 存放下对角线的状态
    int[] downDiagonal;
    /**
     * 构造方法，初始化一些变量
     */
    public EightEmpress(int[] place, int[] flag, int[] upDiagonal, int[] downDiagonal) {
        this.place = place;
        this.flag = flag;
        this.upDiagonal = upDiagonal;
        this.downDiagonal = downDiagonal;
    }
    /**
     * 初始化
     */
    public void init() {
        for (int i = 0; i < this.place.length; i++) {
            this.place[i] = 1;
        }
        for (int i = 0; i < this.flag.length; i++) {
            this.flag[i] = 1;
        }
        for (int i = 0; i < this.upDiagonal.length; i++) {
            this.upDiagonal[i] = 1;
        }
        for (int i = 0; i < this.downDiagonal.length; i++) {
            this.downDiagonal[i] = 1;
        }
    }

    /**
     * 递归实现N皇后算法
     * @param row:棋盘的行
     */
    public void generate(int row) {
        // 遍历列
        for (int col = 0; col < this.place.length; col++) {
            if (this.flag[col] == 1) {

            }
            // 判断位置是否已被占领
            if(this.flag[col] == 1 && this.upDiagonal[row - 1 + col] == 1 && this.downDiagonal[row - 1 - col + 7] == 1) {
                // 摆放皇后
                this.place[row - 1] = col;
                // 占领该列
                this.flag[col] = 0;
                // 占领对角线
                this.upDiagonal[row - 1 + col] = 0;
                this.downDiagonal[row - 1 - col + 7] = 0;
                // 递归条件
                if (row > 1) {
                    generate(row - 1);
                } else {
                    // 计数
                    this.count++;
                }
                // 回溯--撤回皇后、解放列、解放对角线
                this.place[row - 1] = 1;
                this.flag[col] = 1;
                this.upDiagonal[row - 1 + col] = 1;
                this.downDiagonal[row - 1 - col + 7] = 1;
            }
        }
    }
    // main
    public static void main(String[] args) {
        // 创建棋盘
        int row = 8;
        int col = row;
        // 创建变量
        int[] place = new int[row];
        int[] flag = new int[col];
        int[] upDiagonal = new int[row + col - 1];
        int[] downDiagonal = new int[row + col - 1];
        // 实例化对象
        EightEmpress eightEmpress = new EightEmpress(place,flag,upDiagonal,downDiagonal);
        // 初始化
        eightEmpress.init();
        // 调用方法
        eightEmpress.generate(row);
        // 输出解的种类
        System.out.println(eightEmpress.count);
    }
}